MacFormat 1994 November/macformat-018.iso/Utility Spectacular/Developer/Venus/project_3D.cc

Text File | 1994-07-26 | 17.3 KB | 527 lines | [TEXT/ALFA]

// This may look like C code, but it is really -*- C++ -*-
/*
 ************************************************************************
 *
 *                           Rendering of a 3D function
 *
 * Suppose we have a function z=f(x,y) specified as an image, where
 * pixel intensity z at point (x,y) is the value of the function f(x,y).
 * We assume the map (function) is periodic, i.e., f(x+n*Dx,y+m*Dy)=f(x,y)
 * for each integer n and m; Dx and Dy are dimensions of the map. We assume
 * Dx = Dy = D. In the following, we assume that x, y are always within
 * [0,D-1].
 *
 * The coordinate system (x,y,z) is chosen so that x increases along
 * the horizontal lines, z is the elevation, and y increases "in depth".
 *
 * We would use a perspective projection with the center (x0, y0, z0)
 * and the projection plane y=y0+eye_focus. So, the viewer looks from the
 * point (x0,y0,z0) straight "in depth".
 * When performing projection, we project the points of the map with y within
 *         [y0+eye_focus,y0+sight_depth]
 * In doing the projections, we scan the 3D map along the line with y=const
 * from y=y0+sight_depth to y=y0+eye_focus, that is, from farther to closer.
 *
 * Thus, we need to project a volume {x in [0,D), y in [y0+eye_focus,y0+sight_depth],
 * z in [0,Z)} into the view plane {u in (0,Du), v in (0,Dv)}
 * View plane is associated with the eye focal plane (and fixed at the observer,
 * that is, us). We use a perspective transformation: draw a line from a point
 * (x1,y1,z1) of the volume to a view point (x0,y0,z0), and see where the line
 * intersects the view plane y=y0+eye_focus.
 * The equation for the line connecting (x1,y1,z1) with (x0,y0,z0) is
 *    (x-x0)/(x1-x0) = (y-y0)/(y1-y0) = (z-z0)/(z1-z0)
 * The line intersects the plane y=y0+eye_focus at a point
 *    x = x0 + (x1-x0)*factor
 *  z = z0 + (z1-z0)*factor
 *  with factor = eye_focus/(y1-y0)
 * To finish the translation into the view port coordinates, we need to know
 * the projection of our eye: if we look straight into the horizon, that is,
 * y1=infinity, we see a point (x0,y0) at the view plane. We want this point
 * to be suitably located in the view plane, that is, having the view plane
 * coordinates (u=Du/2, v=horizon). It gives us necessary transformation formulas
 * from a point (x,y,z) into the point (u,v) of the view plane
 *    u = Du/2 + (x-x0)*factor
 *  v = horizon + (z-z0)*factor
 *    where
 *        factor = eye_focus/(y-y0)
 * Note that y >= y0+eye_focus always, therefore y>y0. That is, we can't see
 * (at least distinctly) objects very close to our eyes, let alone objects
 * behind our eyes. So, for all y we consider, 0<factor<=1
 *
 * If we scan the map along the line y=const, then 'factor' remains constant
 * during the scan. Of course, we can increment x by one and then find
 * the corresponding point (u,v) on the view plane and draw it.
 * However, since the view plane is what we are going to display, it's
 * better to increment u by one and then work it out back to x, find
 * z value at (x,y) and compute v.
 *
 * So, the algorithm to process the scanline y=const is as follows:
 * 1. fix y=const within [y0+eye_focus,y0+sight_depth] and compute
 *    factor=eye_focus/(y-y0)
 * 2. compute xref = -D/2/factor + x0
 * 3. for u=0 to D-1
 * 4.     compute x=(round)xref
 * 5.     find z=f(x,y) from the map
 * 6.      compute v = factor*(z-z0) + horizon
 * 7.     xref += 1/factor
 *     endfor
 *
 * Note, that the 'factor' should be represented as a fraction, since 0<factor<=1
 * Division and multiplications by the factor are fixed-point arithmetic
 * operations; xref is also a fixed-point number, the others are integers.
 * We also assume that Du (width of the view plane) is equal to D (width of
 * the map), though it isn't so critical.
 *
 * Since we scan from larger y's to smaller y's (that is, from farther ahead
 * to near, that is, towards the observer), then if a (u,v) point generated by
 * the algorithm should obscure (u,v) point generated at an earlier pass
 * (with larger y), it would just overwrite the old point. However, if we just
 * draw (u,v) dots we compute we get a dotty picture. Note, that actually we see
 * a segment of line (x,y,z)-(x1,y-dy,z1). If we just connect two points generated
 * in two consecutive scans, (u,v1) and (u,vold), it wouldn't be always
 * right, because the original line could've been obscured. Suppose that
 * z0 (elevation of the observation point) is high enough (comparable with
 * the hight of the tallest peaks). Then if v(u,y+dy) > v(u,y) for some
 * u and dy>0, then we have a descending slope, and the line is visible.
 * Otherwise the line is on ascending slope, and it couldn't be visible
 * because it will be obscured by the descending slope (which should be
 * closer to us). Note the line from (u,c1) to (u,vold) is a vertical one,
 * and therefore, is very easy to draw (and clip, if necessary).
 *
 * When we create (u,v) map, we assign to the point (u,v) the intensity
 * (color) of the f(x,y) point of the original map. We can use Gouraud
 * interpolation in drawing the line.
 * Generalization: draw boxes (quadraluzation), than we can increase the
 * scanning step in u (or in y) in the algorithm above.
 *
 * For this particular program, we also draw a part of the map as it is
 * (that is, a 2D picture) above the horizon: just to make clouds.
 *
 * Inspiration:
 * Tim Clarke, [e-mail]
 * Note, there are some typos in that post. And my notation is completely different
 * from his.
 *
 ************************************************************************
 */

#include "image.h"
#include "window.h"

#define Debug 0
const short eye_focus = 50;
const short sight_depth = 200;

/*
 *----------------------------------------------------------------------
 *                An instance of a generic screen window to display
 *                                 a "3D" image
 */

class ProjectionWindow : public OffScreenWindow
{
    const IMAGE& map;                    // that specifies z=f(x,y)

    short x0, y0, z0;                    // Point of view
    short hor;                            // Elevation of the horizon on the view plane
    Boolean do_animation;

    void project(void);                    // Draw a projection in an offscreen
                                        // world
                                        // Draw clouds above the horizon
    void draw_clouds(const int horizon, const int starting_y);

                                // A class to handle one scanline of the view plane
    struct OneViewScanline
    {
        const short width;
        short * vs;
        char  * color;

        OneViewScanline(const short _width);
        ~OneViewScanline(void);
                                // Put all zeros (for the final scanline)
        void clear(void);

    };

    OneViewScanline scanline1, scanline2;
    void draw_scanline(OneViewScanline& scanline, const short y);
                                // Connect two scanlines, sl0 to sl1, drawing
                                // vertical lines between corresponding points
                                // (if the lines are visible)
    void connect_scanlines(OneViewScanline& sl0, OneViewScanline& sl1);

                                        // redefining some event handlers
    virtual Boolean handle_key_down(const EventRecord& the_event);
    virtual Boolean handle_null_event(const long event_time);

public:
    ProjectionWindow(const IMAGE& image, const char * title);
    ~ProjectionWindow(void)  {}
};


                                // Creating a window that would have our picture
                                // displayed.
ProjectionWindow::ProjectionWindow(const IMAGE& image, const char * title)
    : OffScreenWindow(ScreenRect(rowcol(256,image.q_ncols())),title,256),
      map(image),
      scanline1(image.q_ncols()),
      scanline2(image.q_ncols()),
      do_animation(FALSE)
{
    x0 = map.q_ncols()/2;            // Pick up the initial observation point
    y0=0;                            // somewhere in the middle
    z0 = 200;
    hor = 100;

    project();
    do_animation = TRUE;
}


                                    // Handles key_down & auto_key events. Return FALSE
                                    // if the window is to be closed down
                                    // The key handled move the observer and/or
                                    // change his direction of view (horizon)
                                    // To the observer (that is, us) it looks like
                                    // the entire scene moves.
Boolean ProjectionWindow::handle_key_down(const EventRecord& the_event)
{
    //message("char pressed %ld",the_event.message & charCodeMask);
    switch(the_event.message & charCodeMask)
    {
        case 11:                // PgUp
             if( the_event.modifiers & optionKey )
               if( hor < 250 )
                 hor++;
               else if( z0 < 250 )
                 z0++;
             break;

        case 12:                // PgDn
             if( the_event.modifiers & optionKey )
               if( hor > 5 )
                 hor--;
               else if( z0 > 0 )
                 z0--;
             break;


        case 30:                // Arrow Up
             if( (y0 +=2) >= map.q_nrows() )
               y0 = 0;
             break;

        case 31:                // Arrow Down
             if( (y0 -=2) < 0 )
               y0 = map.q_nrows()-1;
             break;

        case 28:                // Arrow Left
             if( (x0 -=4) < 0 )
               x0 = map.q_ncols()-1;
             break;

        case 29:                // Arrow Righ
             if( (x0 +=4) >= map.q_ncols() )
               x0 = 0;
             break;

        default:
             return FALSE;                // Other keys kill the application

    }
    project();
    refresh();
    return TRUE;
}


                                    // Handles null events, when nothing happens for some
                                    // time. Return FALSE when it's time to die
                                    // This function changes the view point (that
                                    // is, moves the scene) with the time
                                    // (or with the mouse moves), and makes animation
                                    // When the mouse button is pressed, the
                                    // scene moves with the mouse; otherwise, it
                                    // moves by itself.
Boolean ProjectionWindow::handle_null_event(const long event_time)
{
  static long int prev_tick_count = 0;
  static Point prev_mouse_loc;

  if( prev_tick_count == 0 )
  {
    prev_tick_count = TickCount();
    GetMouse(&prev_mouse_loc);
    return TRUE;
  }

  if( !do_animation )
    return TRUE;

  if( StillDown() )                    // If mouse button is kept pressed, the user
  {                                    // wants to lead the way. Move the picture
      Point new_point;                // as he moves the mouse
      GetMouse(&new_point);
      x0 += (new_point.h - prev_mouse_loc.h)*2;
      y0 -= (new_point.v - prev_mouse_loc.v)*2;
      prev_mouse_loc = new_point;
  }
  else if( TickCount() - prev_tick_count < 20 )
    return TRUE;
  else
  {
    prev_tick_count = TickCount();

    x0 += 4;                                // Move the scene - do animation
    y0 += 4;
  }

  if( x0 >= map.q_ncols())                    // Do some clipping
    x0 = 0;
  else if( x0 < 0 )
    x0 = map.q_ncols()-1;
  if( y0 >= map.q_nrows())
    y0 = 0;
  else if( y0 < 0 )
    y0 = map.q_nrows()-1;

  project();
  refresh();

  return TRUE;                            // Keep going
}



                                // Allocate data for one scanline of the view window
ProjectionWindow::OneViewScanline::OneViewScanline(const short _width)
    : width(_width)
{
                                    // Allocate memory in one chunk for both arrays
    vs = (short *)malloc(width*(sizeof(vs[0])+sizeof(color[0])));
    assert( vs != 0 );
    color = (char *)vs + width*sizeof(vs[0]);
}

                                // Dispose of the arrays
ProjectionWindow::OneViewScanline::~OneViewScanline(void)
{
    assert( vs != 0 );
    delete vs;                        // color would be disposed of, too
}

                                // Put all zeros (for the final scanline)
void ProjectionWindow::OneViewScanline::clear(void)
{
    memset((void *)vs,0,width*sizeof(vs[0]));
    memset((void *)color,0,width*sizeof(color[0]));
}


                                // Draw a scanline, i.e. line of const y for
                                // all u's within 0..width-1
                                // see formulas above
                                // For factor, invfactor, xref we use a fixed-
                                // point arithmetic with 8-bit implied fraction
void ProjectionWindow::draw_scanline(OneViewScanline& scanline, const short y)
{
    int factor = (eye_focus<<8)/(y-y0);
    int invfactor = ((long)(y-y0)<<8)/eye_focus;
                                    // We know that xref = -D/2/factor + x0
                                    // But we want to keep xref positive, moreover,
                                    // within [0,D-1]. Since the map is periodic
                                    // with period D, then we can write
                                    // xref = floor(1/2/factor)*D - (D/2)*(1/factor) + x0
                                    // or,
                                    // xref = D( floor(1/2/factor) - (1/2/factor) ) + x0
                                    //      = -D*frac(1/2/factor) + x0
                                    // In fixed point 8-bit fraction arithmetic, it's elementary
                                    // to separate integer and fractional part of
                                    // the invfactor/2
                                    // It's easy to see that xref we got is within the desired
                                    // interval, give or take one D.
    int xref = (x0<<8) - scanline.width * ( (unsigned char)(invfactor >> 1) );
                                    // Make sure xref is within [0,width) in
                                    // the fixed-point 8-bit fraction arithmetic
    const int width_fp = scanline.width<<8;
    if( xref >= width_fp )
        xref -= width_fp;
    if( xref < 0 )
        xref += width_fp;


    short y_map = y;                // Clip y to the map
    while( y_map >= map.q_nrows() )
        y_map -= map.q_nrows();

#if Debug
    message("draw scanline y=%d, factor %d, xref %d",y,factor,xref);
#endif
    register short * vp;
    register char * cp;
    for(vp=scanline.vs, cp = scanline.color; vp<&scanline.vs[scanline.width]; )
    {
        int x = xref>>8;
        int z = map(y_map,x);
        *vp++ = ((factor*(z-z0))>>8) + hor;
        *cp++ = z;
#if Debug
        if( vp - scanline.vs < 5 )
          message("map(%d,%d) is %d, projected to v=%d",y_map,x,z,*(vp-1));
#endif
        if( (xref += invfactor) >= width_fp )
          xref -= width_fp;
    }
}


                                    // Draw a projection in an offscreen
                                    // graf world
void ProjectionWindow::project(void)
{
//    SetOffscreenWorld offscreen_world(*this);

//    ScreenRect sub_horizon(q_bounds());
//    sub_horizon.top +=40; //= sub_horizon.bottom-z0;
//    sub_horizon.print("sub horizon");
//    EraseRect(sub_horizon);

    draw_clouds(hor,eye_focus);

    OneViewScanline * curr_scanline = &scanline1,
                    * prev_scanline = &scanline2;
                                                // note curr_scanline ^ pointer_diff
                                                // gives prev_scanline, and
                                                // vice versa
    int pointer_diff = (long int)curr_scanline ^ (long int)prev_scanline;

    draw_scanline(*prev_scanline,y0+sight_depth);

    register int y;
    for(y=y0+sight_depth-1; y >= y0 + eye_focus; y--)
    {
#if Debug
        if((y0+sight_depth-1)-y > 3 )
          exit(0);
#endif
        draw_scanline(*curr_scanline,y);

        connect_scanlines(*prev_scanline,*curr_scanline);

                                            // exchange pointers
        curr_scanline = (OneViewScanline*)((long int)curr_scanline ^ pointer_diff);
        prev_scanline = (OneViewScanline*)((long int)prev_scanline ^ pointer_diff);
//        (long int&)prev_scanline ^= pointer_diff;
    }
}

                                // Connect two scanlines, sl0 to sl1, drawing
                                // vertical lines between the corresponding points
                                // (if the lines are visible)
void ProjectionWindow::connect_scanlines(
    OneViewScanline& sl0, OneViewScanline& sl1)
{
    PixMapHandle pixmap = get_pixmap();

    assert( LockPixels(pixmap) );

    char * pixp = GetPixBaseAddr(pixmap);
    register int u;
    for(u=0; u<width(); u++)                    // Draw a vertical line (u,v)-(u,vold)
    {                                            // (providing it's visible)
      int vold = sl0.vs[u];
      int v    = sl1.vs[u];
      if( v > vold )
        continue;                    // The line is on the ascending slope and *will* be obscured later
                                    // Keep in mind that v <= vold now
      if( v >= height() || vold <= 0 )
        continue;                    // means both v and vold are out-of-picture

      if( v < 0 )
        v = 0;
                                    // Now, 0<=v <= vold
      int z0    = (unsigned char)sl0.color[u]<<4;    // For the purpose of color interpolation
      int z     = (unsigned char)sl1.color[u]<<4;    // we use fixed-point arithmetic with 4 bit
      int stretch = v == vold ? 0 : (z0-z)/(vold-v);// implicit fraction
#if Debug
    if(u<4)
      message("u=%ld drawing from v=%ld to vold=%ld at zs %lx-%lx",u,v,vold,z>>4,z0>>4);
#endif
                                      // draw a line from v to vold
                                      // Note that v on mac goes from top to bottom,
                                      // that is, we need a flip
      char * pixp_beg = pixp + u + (height()-1-v) * bytes_per_row();
//      *pixp_beg = 126;
      for(; v <= (vold > height()-1 ? height()-1 : vold); v++,pixp_beg -= bytes_per_row())
          *pixp_beg = z>>4,
          z += stretch;
    }

    UnlockPixels(pixmap);
}

                                // Draw clouds above the horizon line
                                // using the same map
                                // Simply speaking, just copy a rectangular
                                // segment of the map with y from 0 to
                                // horizon into the offscreen world
                                // Below the horizon, fill everything (I mean,
                                // the offscreen world) with the
                                // background "pixel"
void ProjectionWindow::draw_clouds(const int horizon, const int starting_y)
{
    const unsigned char background_pixel = 124;

    assert( horizon >= 0 && horizon < height() );

    PixMapHandle pixmap = get_pixmap();

    assert( LockPixels(pixmap) );

    char * pixp = GetPixBaseAddr(pixmap);
    char * pixp_stop = pixp + (height()-horizon)*bytes_per_row();
    register int i;                                // "Draw" the image
    for(i=starting_y; pixp<pixp_stop; i++, pixp += bytes_per_row()-width())
    {                                            // Note, bytes_per_row is generally GREATER
      register int j;                            // than width, and is always a multiple of 4
      if( i >= map.q_nrows() )
        i = 0;                                    // make wrap-around
      for(j=0; j<width(); j++)
           *pixp++ = map(i,j);
    }

    pixp_stop += horizon*bytes_per_row();        // Continue till the end of pixmap
    for(; pixp<pixp_stop; pixp += bytes_per_row()-width())
    {                                            // Note, bytes_per_row is generally GREATER
      register int j;                            // than width, and is always a multiple of 4
      for(j=0; j<width(); j++)
           *pixp++ = background_pixel;
    }

    UnlockPixels(pixmap);
}


/*
 *----------------------------------------------------------------------
 *                        Routing display function
 */

void project_3D(const IMAGE& image, const char * title)
{
#if 0
    IMAGE image(image1);
    register int i,j;
    int ncols = image.q_ncols();
    for(j=-20; j<20; j++)
      for(i=-5; i<5; i++)
        image(eye_focus+i,j+ncols/2) = 128 - 5*abs(i+j),
        image(eye_focus+40+i,j+ncols/2) = 180 - 7*abs(i+j);
#endif
    ProjectionWindow map_projection(image,title);
    map_projection.handle();
}